//package suanfa;
//
//import java.util.*;
//
///**
// * Description:
// * Author:    Dane
// * CreateTime:2024/9/4-下午4:34
// * Since  :   1.0
// * Version:   1.0
// */
//public class Solution6 {
//    public static boolean hasCycle(ListNode head) {
//        HashSet<ListNode> listNodes = new HashSet<>();
//        while (head != null) {
//            if (!listNodes.add(head)) {
//                return true;
//            }
//            head = head.next;
//
//
//        }
//        return false;
//
//    }
//
//    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//        ListNode pre = new ListNode();
//        ListNode cur = pre;
//        int count = 0;
//        while (l1 != null || l2 != null) {
//            int value1 = 0;
//            int value2 = 0;
//            if (l1 != null) {
//                value1 = l1.val;
//            }
//            if (l2 != null) {
//                value2 = l2.val;
//            }
//            int sum = value1 + value2 + count;
//            int currentValue = sum % 10;
//            count = sum / 10;
//            cur.next = new ListNode(currentValue);
//            cur = cur.next;
//            if (l1 != null)
//                l1 = l1.next;
//            if (l2 != null)
//                l2 = l2.next;
//        }
//        if (count != 0) {
//            cur.next = new ListNode(count);
//
//        }
//        return pre.next;
//    }
//
//    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        ListNode result = new ListNode();
//        ListNode temp = result;
//        if (list1 == null && list2 == null) {
//            return null;
//        }
//        while (list1 != null || list2 != null) {
//            int val1 = Integer.MAX_VALUE;
//            int val2 = Integer.MAX_VALUE;
//            if (list1 != null) {
//                val1 = list1.val;
//            }
//            if (list2 != null) {
//                val2 = list2.val;
//            }
//            if (val1 < val2) {
//                temp.next = new ListNode(val1);
//                list1 = list1.next;
//            } else {
//                temp.next = new ListNode(val2);
//                list2 = list2.next;
//            }
//
//            temp = temp.next;
//
//        }
//        return result.next;
//
//
//    }
//
//
//    public ListNode reverseBetween(ListNode head, int left, int right) {
//        if (head == null) {
//            return null;
//        }
//        ListNode tempLeft = head;
//
//        ListNode startPre = null;
//        int val = 1;
//        while (val < left) {
//            val++;
//            startPre = tempLeft;
//            tempLeft = tempLeft.next;
//        }
//        ListNode pre = null;
//        ListNode next = null;
//        int count = 0;
//        int length = right - left;
//        while (count <= length) {
//
//            next = tempLeft.next;
//            tempLeft.next = pre;
//            pre = tempLeft;
//            tempLeft = next;
//            count++;
//        }
//        startPre.next = pre;
//        int count2 = 0;
//        while (count2 < length) {
//            count2++;
//            startPre = startPre.next;
//        }
//        startPre.next = tempLeft;
//
//        return head;
//    }
//
//    public static int maxDepth(TreeNode root) {
//
//        if (root == null)
//            return 0;
//        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
//
//
//    }
//
//    public boolean isSameTree(TreeNode p, TreeNode q) {
//        if (p == null && q == null) {
//            return true;
//        }
//        if ((p == null && q != null) || (p != null && q == null))
//            return false;
//
//        boolean leftFlag = isSameTree(p.left, q.left);
//        if (!leftFlag)
//            return false;
//        boolean rightFlag = isSameTree(p.right, q.right);
//        if (!rightFlag)
//            return false;
//
//
//        return p.val == q.val;
//
//
//    }
//
//    public TreeNode invertTree(TreeNode root) {
//        if (root == null) {
//            return null;
//        }
//
//        TreeNode treeNodeLeft = invertTree(root.left);
//        TreeNode treeNodeRight = invertTree(root.right);
//        root.right = treeNodeLeft;
//        root.left = treeNodeRight;
//        return root;
//
//    }
//
//    public boolean isSymmetric(TreeNode root) {
//        if (root == null) {
//            return true;
//        }
//
//
//        return isSameLeftAndRight(root.left, root.right);
//
//    }
//
//    public boolean isSameLeftAndRight(TreeNode left, TreeNode right) {
//        if (left == null && right == null) {
//            return true;
//        }
//        if ((left == null || right == null) || left.val != right.val) {
//            return false;
//        }
//        return isSameLeftAndRight(left.left, right.right) && isSameLeftAndRight(left.right, right.left);
//
//    }
//
//    public static int climbStairs(int n) {
//
//        if (n <= 0) {
//            return 0;
//        }
//        if (n == 1) {
//            return 1;
//        }
//        if (n == 2) {
//            return 2;
//        }
//        int[] dp = new int[n + 1];
//        dp[0] = 0;
//        dp[1] = 1;
//        dp[2] = 2;
//        for (int i = 3; i < n + 1; i++) {
//            dp[i] = dp[i - 1] + dp[i - 2];
//        }
//        return dp[n];
//
//    }
//
//    public static int rob(int[] nums) {
//
//        if (nums.length == 0) {
//            return 0;
//        }
//        if (nums.length == 1) {
//            return nums[0];
//        }
//        int length = nums.length;
//        int[] dp = new int[length];
//
//        dp[0] = nums[0];
//        dp[1] = Math.max(nums[0], nums[1]);
//        for (int i = 2; i < length; i++) {
//            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
//        }
//        return dp[length - 1];
//
//
//    }
//
//    public static int coinChange(int[] coins, int amount) {
//        if (amount == 0) {
//            return 0;
//        }
//        Arrays.sort(coins);
//        ArrayList<Integer> integers = new ArrayList<>();
//        for (int i : coins) {
//            integers.add(i);
//        }
//        int result = 0;
//        int count = 0;
//        int more = 0;
//        while (true) {
//            int max = 0;
//            if (integers.size() == 0) {
//                return -1;
//            }
//            int index = -1;
//            for (int i = integers.size() - 1; i >= 0; i--) {
//                int k = integers.get(i);
//                if (amount >= k) {
//                    max = k;
//                    index = i;
//                    break;
//                }
//            }
//            if (max == 0) {
//                return -1;
//            }
//            count = amount / max;
//            result += count;
//            more = amount % max;
//            if (more != 0) {
//                amount = more;
//
//                integers.remove(index);
//
//
//            } else {
//                return result;
//            }
//        }
//
//    }
//
//
//    public static int searchInsert(int[] nums, int target) {
//        int left = 0;
//        int right = nums.length - 1;
//
//
//        while (left < right) {
//            int mid = (left + right) / 2;
//            if (target == nums[mid]) {
//                return mid;
//            } else if (target > nums[mid]) {
//                left = mid + 1;
//            } else if (target < nums[mid]) {
//                right = mid - 1;
//            }
//        }
//        if (target > nums[left]) {
//            return left + 1;
//        } else {
//            return left;
//        }
//
//    }
//
////    public int numIslands(char[][] grid) {
////
////    }
////    public List<Integer> findNumOfLand(char []grid){
////        boolean flag=false;
////        int count=0;
////    for(int i=0;i<=grid.length;i++){
////        if (grid[i]=='1'){
////
////        }
////    }
////    }
//
//    public int maxArea(int[] height) {
//        if (height.length == 0) {
//            return 0;
//        }
//        if (height.length == 1) {
//            return height[0];
//        }
//        int left = 0;
//        int right = height.length - 1;
//        int result = 0;
//        while (left <= right) {
//            int higher = Math.max(height[left], height[right]);
//            int length = right - left;
//            int area = higher * length;
//            result = Math.max(area, result);
//        }
//        return result;
//
//    }
//
//
//
//    public static TreeNode buildTree(int[] preorder, int[] inorder) {
//        if (preorder.length == 0) {
//            return null;
//        }
//        int rootValue=preorder[0];
//        TreeNode root = new TreeNode(rootValue);
//        int length=preorder.length;
//        if (length == 1) {
//            return root;
//        }
//        int index=-1;
//        for (int i = 0; i < inorder.length; i++) {
//
//            if (inorder[i]==rootValue)
//                index=i;
//        }
//
//
//        int[] leftInOrder = Arrays.copyOfRange(inorder, 0, index);
//        int[] rightInOrder = Arrays.copyOfRange(inorder, index+1, inorder.length);
//
//        int []leftPreOrder=Arrays.copyOfRange(preorder,1,leftInOrder.length+1);
//        int []rightPreOrder=Arrays.copyOfRange(preorder,leftInOrder.length+1,preorder.length);
//
//
//        root.left = buildTree(leftPreOrder,leftInOrder);
//        root.right = buildTree(rightPreOrder,rightInOrder);
//        return root;
//    }
//
//    public boolean hasPathSum(TreeNode root, int targetSum) {
//        if (root==null) {
//            return  false;
//        }
//        if (root.val==targetSum&&root.left==null&&root.right==null){
//            return true;
//        }
//
//        return hasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);
//
//
//    }
//
//
//
//    public static void main(String[] args) {
//
////        int nums[] = {1, 3};
//////        int amount = 6249;
//////        System.out.println(coinChange(nums, amount));
////        System.out.println(searchInsert(nums, 2));
//
//        int nums[] = {1, 8, 6, 2, 5, 4, 8, 3, 7};
//       int [] preorder = {3,9,20,15,7};
//       int []inorder = {9,3,15,20,7};
//        System.out.println(buildTree(preorder,inorder));
//
//
//    }
//}
